/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-29
 * Time: 20:57
 */
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length - 1;
        // 如果最左边 < 最右边
        // 说明本身就没有进行旋转
        if(array[left] < array[right]){
            return array[left];
        }
        while (left < right){
            // right == left + 1
            // 就说明遇到正确结果了, 因为我们要找的是最小的, 并不是确定的某个值
            if(right == left + 1){
                // 返回右边的值, 原因是由下面的转移可知
                // left 取的是大的值, right 取的值是小的值
                return array[right];
            }
            int mid = (left + right) >> 1;
            // mid 与 left , right 比都行, 满足其中一个条件就可以确定是在哪个区间
            if(array[left] < array[mid] || array[mid] >  array[right]){
                left = mid;
            }else if (array[left] > array[mid] || array[mid] <  array[right]){
                right = mid;
            }else if(array[left] == array[mid] && array[mid] == array[right]){
                // 如果左中右三个值都没有办法进行比较, 那么就没有办法判定, 只能线性遍历
                int min = array[left];
                for (int i = left + 1; i <= right; i++) {
                    min = Math.min(array[i], min);
                }
                return min;
            }
        }
        // 没找到
        return -1;
    }
}
